class Solution {
public:
    vector<vector<int>> combine(int n, int k)
    {
        vector<vector<int>> ans;
        vector<int> path;
        vector<bool> check(n + 1, false);
        function<void(int, int)> dfs = [&](int i, int x) {
            if (i == k)
            {
                ans.push_back(path);
                return;
            }
            for (int j = x; j <= n; j++)
            {
                path.push_back(j);
                dfs(i + 1, j + 1);
                path.pop_back();
            }
            };
        dfs(0, 1);
        return ans;
    }
};